package com.dzu.hard;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ZhaoDong
 * @date 2022/12/29 10:22
 * @description 32. 最长有效括号
 */
public class Test32 {

    public static void main(String[] args) {
//        System.out.println(longestValidParentheses(")()())"));
//        System.out.println(longestValidParentheses("(()"));
//        System.out.println(longestValidParentheses("()"));
        System.out.println(longestValidParentheses("())((())"));
    }

    public static int longestValidParentheses(String s) {
        int length = s.length();
        if (length == 0) {
            return length;
        }
        int resp = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(-1);

        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.addLast(i);
            } else {
                stack.pollLast();
                if (stack.isEmpty()) {
                    stack.addLast(i);
                } else {
                    resp = Math.max(resp, i - stack.peekLast());
                }
            }
        }
        return resp;
    }
}
